package gui;

import java.awt.Font;

import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.List;

import javax.swing.AbstractButton;
import javax.swing.ButtonGroup;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JRadioButton;
import javax.swing.UIManager;
//此类用于输出导游线路图
public class RouteMap extends JFrame {
	private JPanel routeMapPanel;

	public RouteMap() {
		super("输出导游线路图");
		setSize(1000, 700);
		setLocation(400, 150);
		Font font = new Font("宋体", Font.PLAIN, 25);
		UIManager.put("OptionPane.font", font);
		UIManager.put("OptionPane.messageFont", font);
		UIManager.put("OptionPane.buttonFont", font);
		setVisible(true);
	}
	//实例化一个scenic对象
	function.Scenic scenic = new function.Scenic();
	int MAX_VALUE = 32767;
	//获取景点数量
	int scenicAmount = scenic.getTotalNumber();
	function.AdjacencyMatrix am = new function.AdjacencyMatrix(scenicAmount);

	public void routeMapPanel() {
		routeMapPanel = new JPanel();
		routeMapPanel.setLayout(null);


		JLabel informationLabel1 = new JLabel("出入口:");
		informationLabel1.setBounds(250, 50, 200, 50);
		informationLabel1.setFont(new Font("宋体", Font.PLAIN, 25));
		routeMapPanel.add(informationLabel1);
		//将所有景点以按钮的形式在界面显示出来用于方便用户选择出入口
		ButtonGroup group1 = new ButtonGroup();
		ArrayList<String> list1 = scenic.display();
		for (int i = 0; i < list1.size(); i++) {
			JRadioButton rb = new JRadioButton(list1.get(i), true);
			rb.setBounds(250, 100 + 30 * i, 200, 30);
			rb.setFont(new Font("宋体", Font.PLAIN, 25));
			routeMapPanel.add(rb);
			group1.add(rb);
		}
		//informationLabel用于显示计算出的最短遍历路程以及路线图
		JLabel informationLabel = new JLabel("");
		informationLabel.setBounds(500, 50, 400, 400);
		informationLabel.setFont(new Font("宋体", Font.PLAIN, 25));
		routeMapPanel.add(informationLabel);
//用户选择好出入口后点击输出按钮即可在界面打印对应的路线和最短路程
		JButton button = new JButton("输出");
		button.setBounds(270, 520, 100, 40);
		button.setFont(new Font("宋体", Font.PLAIN, 25));
		routeMapPanel.add(button);
		button.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) {
				//startScenic为用户选中景点的景点编号
				int startScenic = 0;
				//获取buttongroup中选中按钮的文本----获取用户选择的出入口
				Enumeration<AbstractButton> radioBtns = group1.getElements();
				AbstractButton btn;
				while (radioBtns.hasMoreElements()) {
					btn = radioBtns.nextElement();
					if (btn.isSelected()) {
						startScenic = Integer.parseInt(btn.getText().split("  ")[0]);
						break;
					}
				}
			//调用prim方法计算最短路程和路线
				am.set(0, 3, 14);
				am.set(3, 9, 20);
				am.set(5, 8, 19);
					String information=hamilton(startScenic);
//					将计算结果在界面中打印出来
					informationLabel.setText(information);
				
				
			}
		});

		routeMapPanel.setVisible(true);
		add(routeMapPanel);
		setVisible(true);
	}

	//此方法被hamilton方法调用，用于打印路径
		public String display(int cycle[]) {
			String information="";
			int i;
			//首先加入起点
			information+=scenic.findNameByNumber(cycle[0] );
//			循环加入路径上的其他景点
			for (i = 1; i < scenicAmount; i++) {
				information+="->"+scenic.findNameByNumber(cycle[i] );
			}
//			终点和起点相同，构成回路
			information+="->"+scenic.findNameByNumber(cycle[0] );
			return information;
		}
	//此方法计算最短哈密尔顿回路
		public String hamilton(int start) {
			//构建景点邻接矩阵
			am.create();
			//information用于构建在界面上显示的内容
			String information="<html><body>";
			//cycle数组用于保存整个哈密尔顿回路
			int[] cycle = new int[scenicAmount+1];
			//visited数组用于标识结点是否被访问过
			int[] visited = new int[scenicAmount]; 
			int next, i, j, flag = 0;
			int[] min_path = new int[scenicAmount];
			float temp, old_temp = 10000000;
			/* 初始化visited数组 */
			for (i = 0; i < scenicAmount; i++) 
			{
				visited[i] = 0;
			}
			visited[start-1] = 1; /* 访问起点结点 */
			//将start加入回路中
			cycle[0] = start-1; 
			cycle[1] = 0; 
			//下一个景点标志next
			next = 1; 

			while (true) {
				for (i = cycle[next]; i < scenicAmount; i++) /* 循环找出下一个结点 */
				{//若前一个结点到此结点的距离不为0且不为32767且此结点尚未访问过
					if (am.get(cycle[next - 1], i) != 0 && am.get(cycle[next - 1], i) != MAX_VALUE && visited[i] == 0)
						break;
				}
				if (i < scenicAmount) { /* 如果找到了下一个要访问的结点 */
					cycle[next] = i;/* 将新找到的结点加入回路中*/
					visited[cycle[next]] = 1;/* 访问该结点 */
					/* 如果己经访问了所有结点,而且最后一个结点和初始结点有边相连
					 * 则找到一条哈密尔顿回路
					 *  */
					if (next == scenicAmount - 1 && am.get(cycle[next], start-1) != 0 && am.get(cycle[next], start-1) != MAX_VALUE)
					{ //temp保存当前得到的哈密尔顿回路的路程长度
						temp = 0;
						flag = 1;
						for (j = 0; j < next; j++)/* 求出这条哈密尔顿回路的路程长度 */
						{
							temp += am.get(cycle[j], cycle[j + 1]);
						}
						temp += am.get(cycle[next], start-1);
//						如果当前新构建的哈密尔顿回路的路程长度小于之前的最小长度
						if (temp < old_temp)
						{//循环保存当前构建的路径到min_path中
							for (j = 0; j < scenicAmount; j++) {
								min_path[j] = cycle[j];
							}
							old_temp = temp;
						}
//						重置visited数组
						visited[cycle[next]] = 0;
						visited[cycle[--next]] = 0;
						if (next == 0)/* 找不到更多路径了 */
						{
							if (flag == 1) {
								//输出完整的路线
								information+=display(min_path);
								break;
							}
						}
						//已经找到最短路径，退出循环
						cycle[next]++;
					} else {
						cycle[++next] = 0;
					}
				} else { /* 如果没有找到下一个要访问的结点 */
					visited[cycle[--next]] = 0; /* 回溯 */
					if (next == 0) {
						if (flag == 1)/* 显示己找到的路径 */
						{
							information+=display(min_path);
							break;
						}
					}
					cycle[next]++; /* 移到下一个 */
				}
			}
			return information;
		}
	

}
